{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Degree of an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findShortestSubArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非空且只包含非负数的整数数组&nbsp;<code>nums</code>，数组的 <strong>度</strong> 的定义是指数组里任一元素出现频数的最大值。</p>\n",
    "\n",
    "<p>你的任务是在 <code>nums</code> 中找到与&nbsp;<code>nums</code>&nbsp;拥有相同大小的度的最短连续子数组，返回其长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,2,3,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。\n",
    "连续子数组里面拥有相同度的有如下所示：\n",
    "[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]\n",
    "最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,2,3,1,4,2]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "数组的度是 3 ，因为元素 2 重复出现 3 次。\n",
    "所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length</code>&nbsp;在 <code>1</code> 到 <code>50,000</code> 范围内。</li>\n",
    "\t<li><code>nums[i]</code>&nbsp;是一个在 <code>0</code> 到 <code>49,999</code> 范围内的整数。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [degree-of-an-array](https://leetcode.cn/problems/degree-of-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [degree-of-an-array](https://leetcode.cn/problems/degree-of-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,3,1]', '[1,2,2,3,1,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        #1.先找到度，用字典统计，再找最大统计数，即为度\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else: \n",
    "                dic[i] = 1\n",
    "        du = 0\n",
    "        for i in dic:\n",
    "            if du < dic[i]: du = dic[i]\n",
    "        if du == 1:\n",
    "            return 1\n",
    "         \n",
    "        #根据度找数，找出所有最大度的数\n",
    "        num = []\n",
    "        for i in dic:\n",
    "            if dic[i] == du:\n",
    "                num.append(i)\n",
    "        \n",
    "        #根据数找该数最大最小下标，根据下标计算最短连续子数组\n",
    "        start, end = 0, 0\n",
    "        num_length = []\n",
    "        for i in num:\n",
    "            #设置flag,记录最小下标（第一次出现的下标）\n",
    "            flag = 1\n",
    "            for j in range(len(nums)):\n",
    "                #不断更新最大下标\n",
    "                if nums[j] == i:\n",
    "                    end = j\n",
    "                #记录第一次的下标\n",
    "                if flag == 1:\n",
    "                    if nums[j] == i:\n",
    "                        start = j\n",
    "                        flag -= 1\n",
    "            num_length.append(end-start+1)\n",
    "        return min(num_length)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        degree = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n not in degree:\n",
    "                degree[n] = [1, i, i]\n",
    "                continue\n",
    "            times, left, right = degree[n]\n",
    "            degree[n] = [times + 1, left, i]\n",
    "        max_degree, *_ = sorted(degree.values(), key=lambda x: (-x[0], x[2] - x[1]))\n",
    "        return max_degree[2] - max_degree[1] + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        total=Counter(nums)\n",
    "        max_value=max(total.values())\n",
    "        max_key=[k for k,v in total.items() if v==max_value]\n",
    "        list_value=[]\n",
    "        for i in max_key:\n",
    "            star=None\n",
    "            end=0\n",
    "            for q,j in enumerate(nums):\n",
    "                if i == j and star==None:\n",
    "                    star=q\n",
    "                    end = q\n",
    "                elif i==j:\n",
    "                    end=q\n",
    "            list_value.append(end-star+1)\n",
    "        return min(list_value)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        count = {}\n",
    "        for num in nums:\n",
    "            count[num] = count.get(num,0)+1\n",
    "        max_value = max(count.values())\n",
    "        max_elements = [key for key, value in count.items() if value == max_value]\n",
    "        min_len = len(nums)\n",
    "        for ele in max_elements:\n",
    "            l, r = 0, len(nums)-1\n",
    "            while nums[l] != ele:\n",
    "                l+=1\n",
    "            while nums[r] != ele:\n",
    "                r-=1\n",
    "            min_len = min(min_len, r-l+1)\n",
    "        return min_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        # 找到数组出现频数最大的元素（map记录），然后在数组中找它第一次和最后一次出现的位置即可\n",
    "        mp = dict()\n",
    "        for i in nums:\n",
    "            if i not in mp.keys():\n",
    "                mp[i] = 1\n",
    "            else:\n",
    "                mp[i] += 1\n",
    "        x = []\n",
    "        cnt = 0\n",
    "        for k, v in mp.items():\n",
    "            if v > cnt:\n",
    "                x.clear()\n",
    "                x.append(k)\n",
    "                cnt = v\n",
    "            elif v == cnt:\n",
    "                x.append(k)\n",
    "        # 查找\n",
    "        ans = len(nums)\n",
    "        for i in x:\n",
    "            start = -1\n",
    "            end = -1\n",
    "            for j in range(len(nums)):\n",
    "                if (nums[j] == i):\n",
    "                    start = j\n",
    "                    break\n",
    "            for k in range(len(nums)-1, -1, -1):\n",
    "                if (nums[k] == i):\n",
    "                    end = k\n",
    "                    break\n",
    "            ans = min(ans, end - start + 1)\n",
    "        return ans\n",
    "        \n",
    "                \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        left, right = dict(), dict()\n",
    "        counter = collections.Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in left:\n",
    "                left[num] = i\n",
    "            right[num] = i\n",
    "            counter[num] += 1\n",
    "        degree = max(counter.values())\n",
    "        res = len(nums)\n",
    "        for k, v in counter.items():\n",
    "            if v == degree:\n",
    "                res = min(res, right[k] - left[k] + 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        # 统计每个数字出现的频数和首尾位置\n",
    "        count = {}\n",
    "        first_occurrence = {}\n",
    "        last_occurrence = {}\n",
    "        max_degree = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in count:\n",
    "                count[num] = 1\n",
    "                first_occurrence[num] = i\n",
    "            else:\n",
    "                count[num] += 1\n",
    "            last_occurrence[num] = i\n",
    "            max_degree = max(max_degree, count[num])\n",
    "\n",
    "        # 计算具有最大度的数字的最短连续子数组长度\n",
    "        min_length = float('inf')\n",
    "        for num, degree in count.items():\n",
    "            if degree == max_degree:\n",
    "                min_length = min(min_length, last_occurrence[num] - first_occurrence[num] + 1)\n",
    "\n",
    "        return min_length\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        left, right = dict(),dict()\n",
    "        counter = collections.Counter()\n",
    "        for i, num  in enumerate(nums):\n",
    "            if num not in left:\n",
    "                left[num] = i\n",
    "            right[num] = i\n",
    "            counter[num] += 1\n",
    "        degree = max(counter.values())\n",
    "        res = len(nums)\n",
    "        for k, v in counter.items():\n",
    "            if v == degree:\n",
    "                res = min(res,right[k]-left[k]+1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        num_times = {}\n",
    "        for num in nums:  # 计算每个数的频数\n",
    "            num_times.setdefault(num, 0)  # 设置键 num，若不存在则创建，值为0；若存在则不改变键值\n",
    "            num_times[num] += 1\n",
    "        times = num_times.values()  # 字典值的视图对象，存放每个数的频数\n",
    "        max_du = max(times)  # 求出最大频数，即数组的度\n",
    "        if max_du == 1:\n",
    "            return 1\n",
    "        out = len(nums)\n",
    "        for k, v in num_times.items():  # 遍历字典键值对的视图对象\n",
    "            if v == max_du:  # 找到最大度的数\n",
    "                # 遍历数组，判断此数在数组的最小和最大索引，从而计算出此数的最短连续子数组\n",
    "                min_index = len(nums)  # 最小索引\n",
    "                max_index = 0  # 最大索引\n",
    "                for i in range(len(nums)):\n",
    "                    if nums[i] == k:\n",
    "                        if i < min_index:\n",
    "                            min_index = i\n",
    "                        if i > max_index:\n",
    "                            max_index = i\n",
    "                tmp = max_index - min_index + 1\n",
    "                if tmp < out:\n",
    "                    out = tmp\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        left,rigth = dict(),dict()\n",
    "        counter = collections.Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in left:\n",
    "                left[num] = i\n",
    "            rigth[num] = i\n",
    "            counter[num] += 1\n",
    "        degree = max(counter.values())\n",
    "        res = len(nums)\n",
    "        for k,v in counter.items():\n",
    "            if v == degree:\n",
    "                res = min(res,rigth[k] -left[k]+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        left,right = dict(),dict()\n",
    "        counter = collections.Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in left:\n",
    "                left[num] = i\n",
    "            right[num] = i\n",
    "            counter[num] += 1\n",
    "        degree = max(counter.values())\n",
    "        res = len(nums)\n",
    "        for k,v in counter.items():\n",
    "            if v == degree:\n",
    "                res = min(res,right[k]-left[k]+1)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        left,rigth = dict(),dict()\n",
    "        counter = collections.Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in left:\n",
    "                left[num] = i\n",
    "            rigth[num] = i\n",
    "            counter[num] += 1\n",
    "        degree = max(counter.values())\n",
    "        res = len(nums)\n",
    "        for k,v in counter.items():\n",
    "            if v == degree:\n",
    "                res = min(res,rigth[k] -left[k]+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        counter = Counter(nums)\n",
    "\n",
    "        left, right = dict(), dict()\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in left:\n",
    "                left[num] = i\n",
    "            right[num] = i\n",
    "        degree = max(counter.values())\n",
    "        res = len(nums)\n",
    "        for k, v in counter.items():\n",
    "            if v == degree:\n",
    "                res = min(res, right[k] - left[k] + 1)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = collections.Counter(nums)\n",
    "        count = max(list(cnt.values()))\n",
    "        du = []\n",
    "        res = []\n",
    "        for i in cnt.keys():\n",
    "            if cnt[i] == count:\n",
    "                du.append(i)\n",
    "\n",
    "        for num in du:\n",
    "            for i in range(n):\n",
    "                if nums[i] == num:\n",
    "                    j = i\n",
    "                    rest = count\n",
    "                    while rest > 0:\n",
    "                        if nums[j] == num:\n",
    "                            rest -= 1\n",
    "                        j += 1\n",
    "                    res.append(j-i)\n",
    "                    break\n",
    "        return min(res)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        ans = []\n",
    "        cnt = defaultdict(int)\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "        du = max([v for v in cnt.values()])\n",
    "        for k,v in cnt.items():\n",
    "            l, r = 0, len(nums) - 1\n",
    "            if v == du:\n",
    "                while nums[l] != k:\n",
    "                    l += 1\n",
    "                while nums[r] != k:\n",
    "                    r -= 1\n",
    "            ans.append(abs(r - l) + 1)\n",
    "        return 1 if du == 1 else min(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        left,right = dict(),dict()\n",
    "        conuter = collections.Counter()\n",
    "        for i,num in enumerate(nums):\n",
    "            if num not in left:\n",
    "                left[num] = i\n",
    "            right[num] = i\n",
    "            conuter[num] += 1\n",
    "        degree = max(conuter.values())\n",
    "        res = len(nums)\n",
    "        for k,v in conuter.items():\n",
    "            if v == degree:\n",
    "                res = min(res,right[k]-left[k]+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        dt = {}\n",
    "        for i in range(len(nums)):\n",
    "            cur = nums[i]\n",
    "            if cur in dt:\n",
    "                num = dt[cur][0] + 1\n",
    "                start = dt[cur][1]\n",
    "                end = i\n",
    "            else:\n",
    "                num = 1\n",
    "                start = i\n",
    "                end = i\n",
    "            dt[cur] = (num, start, end)\n",
    "        ans = sorted(dt, key=lambda k: dt[k][0], reverse=True)\n",
    "        max_num = dt[ans[0]][0]\n",
    "        min_num = dt[ans[0]][2] - dt[ans[0]][1] + 1\n",
    "        for i in ans:\n",
    "            if dt[i][0] != max_num:\n",
    "                break\n",
    "            else:\n",
    "                length = dt[i][2] - dt[i][1] + 1\n",
    "                min_num = min(min_num, length)\n",
    "        return min_num\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        counter = dict()\n",
    "        for idx, num in enumerate(nums):\n",
    "            if not num in counter:\n",
    "                counter[num] = (1, idx, idx,)\n",
    "            else:\n",
    "                counter[num] = (counter[num][0]+1, counter[num][1], idx,)\n",
    "        degree = 0\n",
    "        res = 0\n",
    "        for i in counter.values():\n",
    "            if i[0] > degree:\n",
    "                degree = i[0]\n",
    "                res = i[2] - i[1] + 1\n",
    "            elif i[0] == degree:\n",
    "                res = min(i[2] - i[1] + 1, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        dic={}\n",
    "        du,length=0,0\n",
    "        for i,num in enumerate(nums):\n",
    "            if num not in dic:\n",
    "                dic[num]=[1,i,i]\n",
    "            else:\n",
    "                dic[num][0]+=1\n",
    "                dic[num][2]=i\n",
    "        for i in dic:\n",
    "            if dic[i][0]>du:\n",
    "                du=dic[i][0]\n",
    "                length=dic[i][2]-dic[i][1]+1\n",
    "            elif dic[i][0]==du:\n",
    "                if dic[i][2]-dic[i][1]+1<length:\n",
    "                    length=dic[i][2]-dic[i][1]+1\n",
    "                    du=dic[i][0]\n",
    "   \n",
    "        return length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        maxn=0\n",
    "        ex=[]\n",
    "        l=[]\n",
    "        for i in nums:\n",
    "            if i in ex:\n",
    "                continue\n",
    "\n",
    "            t=nums.count(i)\n",
    "            ex.append(i)\n",
    "            if t>maxn:\n",
    "               l.clear()\n",
    "               l.append(i)\n",
    "               maxn=t\n",
    "            elif t==maxn:\n",
    "               l.append(i)\n",
    "        l2=[]\n",
    "        for i in l:\n",
    "            l2.append(len(nums)-nums[::-1].index(i)-nums.index(i))\n",
    "        return min(l2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        mp = dict()\n",
    "        for i,num in enumerate(nums):\n",
    "            if num not in mp:\n",
    "                mp[num] = [1,i,i]\n",
    "            else:\n",
    "                mp[num][0] += 1\n",
    "                mp[num][2] = i\n",
    "        du,minLen = 0,0\n",
    "        for count,l,r in mp.values():\n",
    "            if count > du:\n",
    "                du = count\n",
    "                minLen = r-l+1\n",
    "            elif count == du:\n",
    "                minLen = min(minLen,r-l+1)\n",
    "        return minLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        hmap = dict()\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in hmap:\n",
    "                hmap[num][0] += 1\n",
    "                hmap[num][2] = i\n",
    "            else:\n",
    "                hmap[num] = [1, i, i]\n",
    "\n",
    "        min_len = inf\n",
    "        max_times = 0\n",
    "        for times, left, right in hmap.values():\n",
    "            if times > max_times:\n",
    "                max_times = times\n",
    "                min_len = right - left + 1\n",
    "            elif times == max_times:\n",
    "                if min_len > (temp := right-left+1):\n",
    "                    min_len = temp\n",
    "        \n",
    "        return min_len\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        hashtb = dict()\n",
    "        du = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if num in hashtb:\n",
    "                hashtb[num][1] = i\n",
    "                hashtb[num][2] += 1\n",
    "            else:\n",
    "                hashtb[num] = [i,i,1]\n",
    "            du = max(du,hashtb[num][2])\n",
    "        res = inf\n",
    "        for h in hashtb.values():\n",
    "            if h[2] == du:\n",
    "                res = min(h[1] - h[0] + 1,res)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        mp = dict()\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in mp:\n",
    "                mp[num][0] += 1\n",
    "                mp[num][2] = i\n",
    "            else:\n",
    "                mp[num] = [1, i, i]\n",
    "        \n",
    "        maxNum = minLen = 0\n",
    "        for count, left, right in mp.values():\n",
    "            if maxNum < count:\n",
    "                maxNum = count\n",
    "                minLen = right - left + 1\n",
    "            elif maxNum == count:\n",
    "                if minLen > (span := right - left + 1):\n",
    "                    minLen = span\n",
    "        \n",
    "        return minLen\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        mp = dict()\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in mp:\n",
    "                mp[num][0] += 1\n",
    "                mp[num][2] = i\n",
    "            if num not in mp:\n",
    "                mp[num] = [1, i, i]\n",
    "        \n",
    "        maxNum = minlen = 0\n",
    "\n",
    "        for count, left , right in mp.values():\n",
    "            if maxNum < count:\n",
    "                maxNum = count\n",
    "                minlen = right - left + 1\n",
    "            elif maxNum == count:\n",
    "                if minlen > (span := right - left + 1):\n",
    "                    minlen = span\n",
    "        return minlen \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: list[int]) -> int:\n",
    "        count = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n not in count.keys():\n",
    "                temp = [1, i, i]\n",
    "                count[n] = temp\n",
    "            else:\n",
    "                count[n][0] += 1\n",
    "                count[n][2] = i\n",
    "        count = list(count.values())\n",
    "        max_value = max([t[0] for t in count])\n",
    "        result = 500001\n",
    "        for t in count:\n",
    "            if t[0] == max_value:\n",
    "                result = min(result, t[2] - t[1] + 1)\n",
    "        return result                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        mp = dict()\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in mp:\n",
    "                mp[num][0] += 1\n",
    "                mp[num][2] = i\n",
    "            else:\n",
    "                mp[num] = [1, i, i]\n",
    "        maxnum = minlen = 0\n",
    "        for count, left, right in mp.values():\n",
    "            if maxnum < count:\n",
    "                maxnum = count\n",
    "                minlen = right - left + 1\n",
    "            elif maxnum == count:\n",
    "                if minlen > (span := right - left + 1):\n",
    "                    minlen = span \n",
    "        return minlen\n",
    "        \n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        mp = dict()\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in mp:\n",
    "                mp[num][0] += 1\n",
    "                mp[num][2] = i\n",
    "            else:\n",
    "                mp[num] = [1, i, i]\n",
    "        \n",
    "        maxNum = minLen = 0\n",
    "        for count, left, right in mp.values():\n",
    "            if maxNum < count:\n",
    "                maxNum = count\n",
    "                minLen = right - left + 1\n",
    "            elif maxNum == count:\n",
    "                if minLen > (span := right - left + 1):\n",
    "                    minLen = span\n",
    "        \n",
    "        return minLen\n",
    "'''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        hash_nums={}\n",
    "        # recodenums=[]\n",
    "\n",
    "        # for num in nums:\n",
    "        #     hash_nums[num]=hash_nums.get(num,0)+1\n",
    "        \n",
    "        # max_degree=max(hash_nums.values())\n",
    "        # for key,value in hash_nums.items():\n",
    "        #     if value==max_degree:\n",
    "        #         recodenums.append(key)\n",
    "        # max_num=max(recodenums)\n",
    "        # left=nums.index(max_num)\n",
    "        # start=left+1\n",
    "        # right=0\n",
    "        # while start<len(nums):\n",
    "        #     if nums[start]==max_num:\n",
    "        #         right=start\n",
    "        \n",
    "        # return right-left\n",
    "        hash_count={}\n",
    "        min_=float('inf')\n",
    "        for i,num in enumerate(nums):\n",
    "            if num in hash_nums:\n",
    "                hash_nums[num][1]=i\n",
    "                hash_count[num]+=1\n",
    "            else:\n",
    "                hash_nums[num]=[i,i]\n",
    "                hash_count[num]=1\n",
    "        max_count=max(hash_count.values())\n",
    "\n",
    "        for key,value in hash_count.items():\n",
    "            if value==max_count:\n",
    "                len_=hash_nums[key][1]-hash_nums[key][0]+1\n",
    "                min_=min(min_,len_)\n",
    "        \n",
    "        return min_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        d_n={}\n",
    "        max_count=1\n",
    "        min_length=1000000\n",
    "        for i in range(len(nums)):\n",
    "            n=nums[i]\n",
    "            if n in d_n:\n",
    "                d_n[n][0]+=1\n",
    "                d_n[n][2]=i\n",
    "                if d_n[n][0]>max_count:\n",
    "                    max_count=d_n[n][0]\n",
    "                    min_length=d_n[n][2]-d_n[n][1]+1\n",
    "                elif d_n[n][0]==max_count:\n",
    "                    if d_n[n][2]-d_n[n][1]+1<min_length:\n",
    "                        min_length=d_n[n][2]-d_n[n][1]+1\n",
    "            else:\n",
    "                d_n[n]=[1,i,i]\n",
    "        if max_count==1:\n",
    "            return 1\n",
    "        return min_length\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "    r = {}\n",
    "    l = len(nums)\n",
    "    for i in range(l):\n",
    "      v = nums[i]\n",
    "      p = r.get(v, [-1, 0, 0])\n",
    "      if -1 == p[0]:\n",
    "        p[0] = i\n",
    "      p[1] = i\n",
    "      p[2] += 1\n",
    "      r[v] = p\n",
    "    t, tl = 0, l\n",
    "    print(f\"r {r}\")\n",
    "    for _, v in r.items():\n",
    "      c = v[2]\n",
    "      l = v[1] - v[0] + 1\n",
    "      if c > t or (c == t and l < tl):\n",
    "        # print(f\"update t {c}\")\n",
    "        t = c\n",
    "        tl = l\n",
    "\n",
    "    return tl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        hashmap = dict()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in hashmap.keys():\n",
    "                hashmap[nums[i]][0] += 1\n",
    "                hashmap[nums[i]][2] = i\n",
    "            else:\n",
    "                hashmap[nums[i]] = [1,i,i]\n",
    "        print(hashmap)\n",
    "        mostfrequent = 0\n",
    "        minlength = 0\n",
    "        for i in hashmap.values():\n",
    "            if mostfrequent < i[0]:\n",
    "                mostfrequent = i[0]\n",
    "                minlength = i[2]-i[1]+1\n",
    "            elif mostfrequent == i[0]:\n",
    "                if minlength > i[2]-i[1]+1:\n",
    "                    minlength = i[2]-i[1]+1\n",
    "        return minlength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in dp:\n",
    "                dp[num] = (dp[num][0] + 1, dp[num][1], i)\n",
    "            else:\n",
    "                dp[num] = (1, i, i)\n",
    "        sorted_nums = sorted(dp.items(), key=lambda x: -x[1][0])\n",
    "        # print(sorted_nums)\n",
    "        ans= sorted_nums[0][1][2] - sorted_nums[0][1][1]+1\n",
    "        for x in sorted_nums:\n",
    "            if x[1][0] == sorted_nums[0][1][0]:\n",
    "                ans = min(ans, x[1][2] - x[1][1]+1)\n",
    "                print(x, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        max_time = 0\n",
    "        max_lst = []\n",
    "        n = len(nums)\n",
    "        num_time = {num: [0]*3 for num in set(nums)}\n",
    "\n",
    "        for i in range(n):\n",
    "            curr_num = num_time[nums[i]]\n",
    "            curr_num[0] += 1\n",
    "\n",
    "            if curr_num[0] == 1:\n",
    "                curr_num[1] = i \n",
    "            else:\n",
    "                curr_num[2] = i - curr_num[1] + 1\n",
    "\n",
    "            if max_time == curr_num[0]:\n",
    "                max_lst.append(nums[i])\n",
    "            elif max_time < curr_num[0]:\n",
    "                max_time = curr_num[0]\n",
    "                max_lst = [nums[i]]\n",
    "        \n",
    "        if max_time == 1:\n",
    "            return 1\n",
    "\n",
    "        min_len = n\n",
    "        for i in range(len(max_lst)):\n",
    "            if min_len > num_time[max_lst[i]][2]:\n",
    "                min_len = num_time[max_lst[i]][2]\n",
    "    \n",
    "        return min_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, num):\n",
    "        count = dict(zip(set(num),[num.count(i) for i in set(num)]))\n",
    "        max_val = max(count.values())\n",
    "        max_nums = []\n",
    "        for key, val in count.items():\n",
    "            if val == max_val:\n",
    "                max_nums.append(key)\n",
    "\n",
    "        ans = []\n",
    "        for max_num in max_nums:\n",
    "            st = -1\n",
    "            ed = 0\n",
    "            for i, a in enumerate(num):\n",
    "                if a == max_num:\n",
    "                    if st == -1:\n",
    "                        st = i\n",
    "                    ed = i+1\n",
    "            ans.append(ed-st) \n",
    "        return min(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        if not nums or len(nums) < 1:\n",
    "            return 0\n",
    "        ele_map = {}\n",
    "        for i in range(len(nums)):\n",
    "            one = nums[i]\n",
    "            if one not in ele_map:\n",
    "                ele_map[one] = [1, i, i]\n",
    "            else:\n",
    "                ele_map[one][2] = i\n",
    "                ele_map[one][0] += 1\n",
    "        ele_map = sorted(ele_map.items(), key=lambda x: x[1][0], reverse=True)\n",
    "        # print(ele_map)\n",
    "        m_freq = ele_map[0][1][0]\n",
    "        res = float('inf')\n",
    "        for one in ele_map:\n",
    "            if one[1][0] < m_freq:\n",
    "                break\n",
    "            res = min(one[1][2]-one[1][1]+1, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 50000\n",
    "cnter = [0] * N\n",
    "pos = [-1] * N\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        for i in range(N):\n",
    "            cnter[i] = 0\n",
    "            pos[i] = -1\n",
    "        \n",
    "        ans = mx = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            cnter[num] += 1\n",
    "\n",
    "            if pos[num] == -1:\n",
    "                pos[num] = i\n",
    "            \n",
    "            if cnter[num] == mx:\n",
    "                ans = min(ans, i - pos[num])\n",
    "            elif cnter[num] > mx:\n",
    "                mx += 1\n",
    "                ans = i - pos[num]\n",
    "\n",
    "        return ans + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        dict = Counter(nums)\n",
    "        degree = max(dict.values())\n",
    "        elements = []\n",
    "        for key in dict.keys():\n",
    "            if dict[key] == max(dict.values()):\n",
    "                elements.append(key)\n",
    "        count = {}\n",
    "        for element in elements:\n",
    "            position = []\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == element:\n",
    "                    position.append(i)\n",
    "            distance = max(position)-min(position)+1\n",
    "            count.setdefault(element,distance)\n",
    "        return min(count.values())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        tracker = Counter(nums)\n",
    "\n",
    "        tracker = sorted(tracker.items(), key = lambda x: -x[1])\n",
    "        ct = tracker[0][1]\n",
    "        tracker = dict(tracker)\n",
    "\n",
    "        digits = [k for k,v in tracker.items() if v==ct]\n",
    "\n",
    "        maxLen = float(\"inf\")\n",
    "        for digit in digits:\n",
    "            s = nums.index(digit)\n",
    "            e = len(nums) - 1 - nums[::-1].index(digit)\n",
    "            print(s, e)\n",
    "            maxLen = min(maxLen, e-s+1)\n",
    "        return maxLen\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        max_time = 0\n",
    "        max_lst = []\n",
    "        n = len(nums)\n",
    "        num_time = {num: [0]*3 for num in set(nums)}\n",
    "\n",
    "        for i in range(n):\n",
    "            num_time[nums[i]][0] += 1\n",
    "\n",
    "            if num_time[nums[i]][0] == 1:\n",
    "                num_time[nums[i]][1] = i \n",
    "            else:\n",
    "                num_time[nums[i]][2] = i - num_time[nums[i]][1] + 1\n",
    "\n",
    "            if max_time == num_time[nums[i]][0]:\n",
    "                max_lst.append(nums[i])\n",
    "            elif max_time < num_time[nums[i]][0]:\n",
    "                max_time = num_time[nums[i]][0]\n",
    "                max_lst = [nums[i]]\n",
    "        \n",
    "        if max_time == 1:\n",
    "            return 1\n",
    "\n",
    "        min_len = n\n",
    "        for i in range(len(max_lst)):\n",
    "            if min_len > num_time[max_lst[i]][2]:\n",
    "                min_len = num_time[max_lst[i]][2]\n",
    "    \n",
    "        return min_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find_all_indexs(self, num, nums):\n",
    "        res_index = list()\n",
    "        for i, item in enumerate(nums):\n",
    "            if item == num:\n",
    "                res_index.append(i+1)\n",
    "        space = res_index[-1] - res_index[0] + 1\n",
    "        return space\n",
    "\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        nums_dict = Counter(nums)  # {items: frequency, }\n",
    "        # 找到频数最大的值和对应的item\n",
    "        max_freq_s = max(list(nums_dict.values()))\n",
    "        # 如果频率最大为1则说明都只出现一次则最短连续子数组为1\n",
    "        if max_freq_s == 1:\n",
    "            return 1\n",
    "        # sub_dict\n",
    "        sub_dict = dict()\n",
    "        for key, freq in nums_dict.items():\n",
    "            if freq == max_freq_s:\n",
    "                sub_dict[key] = freq\n",
    "\n",
    "        # 寻找含有度的子数组\n",
    "        spaces = list()\n",
    "        for num in sub_dict.keys():\n",
    "            num_space = self.find_all_indexs(num, nums)   # list\n",
    "            spaces.append(num_space)\n",
    "        lens = min(spaces) if len(spaces) > 0 else 0\n",
    "        return lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        m = {}\n",
    "        for num in nums:\n",
    "            if num not in m.keys():\n",
    "                m[num] = 1\n",
    "            else:\n",
    "                m[num] += 1\n",
    "        du = max(m.values())\n",
    "        if du == 1:\n",
    "            return 1\n",
    "\n",
    "        freq = [num for num in m.keys() if m[num] == du]\n",
    "        # print(freq)\n",
    "        # 计算最短连续子数组的长度\n",
    "        ans = float('inf')\n",
    "        for target in freq:\n",
    "            # 计算首个和末个位置\n",
    "            pos = []\n",
    "            for index, num in enumerate(nums):\n",
    "                if num == target:\n",
    "                    pos.append(index)\n",
    "            ans = min(ans, pos[-1]-pos[0]+1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        freq = {}\n",
    "        max_num_ = []\n",
    "        degree = 0\n",
    "        for n in nums:\n",
    "            if freq.get(n, -1) == -1:\n",
    "                freq[n] = 1\n",
    "            else:\n",
    "                freq[n] += 1\n",
    "            if freq[n] > degree:\n",
    "                degree = freq[n]\n",
    "                max_num_ = [n]\n",
    "            elif freq[n] == degree:\n",
    "                max_num_.append(n)\n",
    "\n",
    "        max_num = set(max_num_)\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while max_num:            \n",
    "            # print(i, j, max_num)      \n",
    "            if nums[j] not in max_num:\n",
    "                j -= 1\n",
    "            elif len(max_num) > 1:                \n",
    "                max_num.remove(nums[j])\n",
    "                j -= 1\n",
    "            else:\n",
    "                break\n",
    "        while max_num:\n",
    "            # print(i, j, max_num)\n",
    "            if nums[i] not in max_num:\n",
    "                i += 1\n",
    "            elif len(max_num) > 1:\n",
    "                max_num.remove(nums[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        res = j - i + 1\n",
    "        max_num = set(max_num_)\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while max_num:\n",
    "            # print(i, j, max_num)\n",
    "            if nums[i] not in max_num:\n",
    "                i += 1\n",
    "            elif len(max_num) > 1:\n",
    "                max_num.remove(nums[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        while max_num:            \n",
    "            # print(i, j, max_num)      \n",
    "            if nums[j] not in max_num:\n",
    "                j -= 1\n",
    "            elif len(max_num) > 1:                \n",
    "                max_num.remove(nums[j])\n",
    "                j -= 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        \n",
    "\n",
    "        # print(i, j)\n",
    "        return min(res, j - i + 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        most=set()\n",
    "        dic={}\n",
    "        maxcount=0\n",
    "        ans=50001\n",
    "        for index,i in enumerate(nums):\n",
    "            if i not in dic:\n",
    "                dic[i]=[1,index,index]\n",
    "            else:\n",
    "                dic[i][0]+=1\n",
    "                dic[i][2]=index\n",
    "            if dic[i][0]>maxcount:\n",
    "                maxcount=dic[i][0]\n",
    "                most={i}\n",
    "            elif dic[i][0]==maxcount:\n",
    "                most.add(i)\n",
    "        for i in most:\n",
    "            ans=min(ans,dic[i][2]-dic[i][1]+1)\n",
    "        # print(dic,dicfirst,most)\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     if not most:\n",
    "        #         break\n",
    "        #     elif nums[i] in most:\n",
    "        #         most.remove(nums[i])\n",
    "        #         ans=min(i-dicfirst[nums[i]]+1,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        dic2 = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in dic.keys():\n",
    "                dic[nums[i]] = [i, i]\n",
    "            else:\n",
    "                dic[nums[i]][-1] = i\n",
    "            if nums[i] not in dic2.keys():\n",
    "                dic2[nums[i]] = 1\n",
    "            else:\n",
    "                dic2[nums[i]] += 1\n",
    "        result = []\n",
    "        min1 = 1\n",
    "        for num in set(nums):\n",
    "            if dic2[num]>min1:\n",
    "                result = []\n",
    "                result.append(num)\n",
    "                min1 = dic2[num]\n",
    "            elif dic2[num]==min1:\n",
    "                result.append(num)\n",
    "        return min((dic[i][1]-dic[i][0] + 1) for i in result)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        a = defaultdict(lambda: [0, -1, 0])\n",
    "        for i, n in enumerate(nums):\n",
    "            a[n][0] += 1\n",
    "            if a[n][1] == -1:\n",
    "                a[n][1] = i\n",
    "            a[n][2] = i\n",
    "\n",
    "        r = [(n, ct, r - l + 1) for n, (ct, l, r) in a.items()]\n",
    "        r.sort(key=lambda x: (x[1], -x[2]), reverse=True)\n",
    "        return r[0][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        # N=len(nums)\n",
    "        # times=[0]*N\n",
    "        # closest=[1]*N\n",
    "        # for i in range(N):\n",
    "        #     for j in range(i):\n",
    "        #         if nums[j]==nums[i]:\n",
    "        #             times[j]+=1\n",
    "        #             closest[j]=i-j+1\n",
    "        #             break\n",
    "        \n",
    "        # ret=50000\n",
    "        # for i in range(N):\n",
    "        #     if times[i]==max(times):\n",
    "        #         if closest[i]<ret:\n",
    "        #             ret=closest[i]\n",
    "        # return ret\n",
    "        N=len(nums)\n",
    "        MAX=50000\n",
    "        times=[0]*MAX\n",
    "        firapp=[-1]*MAX\n",
    "        lastapp=[-1]*MAX\n",
    "        for i in range(len(nums)):\n",
    "            times[nums[i]]+=1\n",
    "            if firapp[nums[i]]==-1:\n",
    "                firapp[nums[i]]=i\n",
    "            lastapp[nums[i]]=i\n",
    "        \n",
    "        max_times=max(times)\n",
    "        ret=MAX\n",
    "        for i in range(MAX):\n",
    "            if firapp[i]!=-1:\n",
    "                if times[i]==max_times:\n",
    "                    if lastapp[i]-firapp[i]+1<ret:\n",
    "                        ret=lastapp[i]-firapp[i]+1\n",
    "\n",
    "        return ret\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        # 首先找到list的度degree: 元素出现的最多的那个次数\n",
    "        dic = Counter(nums)\n",
    "        max_key = [key for key, value in dic.items() if value == max(dic.values())]\n",
    "        \n",
    "        digit_cnt = defaultdict(list) \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in max_key:\n",
    "                digit_cnt[nums[i]].append(i)\n",
    "        \n",
    "        \n",
    "        degree = []\n",
    "        for v in  digit_cnt.values():\n",
    "            degree.append(v[-1] - v[0] + 1)\n",
    "                    \n",
    "        return min(degree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        # 计算数组的度，以及最大度的值\n",
    "        set1 = set(nums)\n",
    "        max_deg_element = []\n",
    "        max_deg_value = 0\n",
    "        for r in set1:\n",
    "            count = nums.count(r)\n",
    "            if count > max_deg_value:\n",
    "                max_deg_value = count\n",
    "                max_deg_element=[r]\n",
    "            elif count == max_deg_value:\n",
    "                max_deg_element.append(r)\n",
    "\n",
    "        print(max_deg_value)\n",
    "        print(max_deg_element)\n",
    "        rnums = list(reversed(nums))\n",
    "        print(rnums)\n",
    "        max_len = len(nums)\n",
    "        for v in max_deg_element:\n",
    "            start = nums.index(v)\n",
    "            end = len(nums) - rnums.index(v)\n",
    "            print(start,end)\n",
    "\n",
    "            max_len = min(max_len, len(nums[start:end]))\n",
    "        return max_len\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        counter = collections.Counter(nums)\n",
    "        max_count = max(counter.values())\n",
    "        most_common_nums = [num for num, count in counter.items() if count == max_count]\n",
    "\n",
    "        length_vec = [max([i for i, num in enumerate(nums) if num == common_num]) - min([i for i, num in enumerate(nums) if num == common_num]) + 1 for common_num in most_common_nums]\n",
    "\n",
    "        return min(length_vec)          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                dic[i] += 1\n",
    "        dica=sorted(dic.items(),key=lambda v:v[1],reverse=True)\n",
    "        ls=[]\n",
    "        for k,v in dic.items():\n",
    "            if v==dica[0][1]:\n",
    "                a = [index for index, num in enumerate(nums) if num == k]\n",
    "                b=len(nums[a[0]:a[-1]+1])\n",
    "                ls.append(b)\n",
    "        return min(ls)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        count = defaultdict(int)\n",
    "\n",
    "        for num in nums:\n",
    "            count[num] += 1\n",
    "\n",
    "        data = [[k, v] for k, v in count.items()]\n",
    "        data.sort(key=lambda x:-x[1])\n",
    "\n",
    "        target_num = [data[0][0]]\n",
    "\n",
    "        for item in data[1:]:\n",
    "            if item[1] < data[0][1]:\n",
    "                break\n",
    "            else:\n",
    "                target_num.append(item[0])\n",
    "\n",
    "        tmp = defaultdict(list)\n",
    "        for num in target_num:\n",
    "            tmp[num] = [float('inf'), float('-inf')]\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in tmp:\n",
    "                tmp[nums[i]] = [min(tmp[nums[i]][0], i), max(tmp[nums[i]][1], i)]\n",
    "\n",
    "        \n",
    "        ans = float('inf')\n",
    "        for key, val in tmp.items():\n",
    "            ans = min(ans, val[1] - val[0] + 1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        degree = 0\n",
    "        dp ={}\n",
    "        ans = {}\n",
    "\n",
    "        \n",
    "        for i in range(n):\n",
    "            if nums[i] in dp:\n",
    "                dp[nums[i]][0] = dp[nums[i]][0] + 1\n",
    "            else:\n",
    "                dp[nums[i]]=[1,i]\n",
    "                \n",
    "            if dp[nums[i]][0] >= degree:\n",
    "                degree = dp[nums[i]][0]\n",
    "                if degree in ans:\n",
    "                    ans[degree] = min(ans[degree], i - dp[nums[i]][1] +1)\n",
    "                else:\n",
    "                    ans[degree] = i - dp[nums[i]][1] +1\n",
    "        \n",
    "        return ans[degree]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        def get_sub_array_len(target):\n",
    "            start, end = 0, 0\n",
    "            seq = tuple(enumerate(nums))\n",
    "            for i, n in seq:\n",
    "                if n == target:\n",
    "                    start = i\n",
    "                    break\n",
    "            for i, n in reversed(seq):\n",
    "                if n == target:\n",
    "                    end = i\n",
    "                    break\n",
    "            return end - start + 1\n",
    "\n",
    "        degrees = sorted(Counter(nums).items(), key=lambda x: x[1])\n",
    "        lens = [get_sub_array_len(t) for t, c in degrees if c == degrees[-1][1]]\n",
    "        return min(lens)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        def get_sub_array_len(target):\n",
    "            start, end = 0, 0\n",
    "            for i, n in seq:\n",
    "                if n == target:\n",
    "                    start = i\n",
    "                    break\n",
    "            for i, n in reversed(seq):\n",
    "                if n == target:\n",
    "                    end = i\n",
    "                    break\n",
    "            return end - start + 1\n",
    "\n",
    "        seq = tuple(enumerate(nums))\n",
    "        degrees = sorted(Counter(nums).items(), key=lambda x: x[1])\n",
    "        lens = [get_sub_array_len(t) for t, c in degrees if c == degrees[-1][1]]\n",
    "        return min(lens)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        def getm(nums):\n",
    "            l = Counter(nums)\n",
    "            # print(l)\n",
    "            n = []\n",
    "            m = l.most_common()[0][1]\n",
    "            for x,c in l.most_common():\n",
    "                if c < m:\n",
    "                    break\n",
    "                n.append(x)\n",
    "            return m, n\n",
    "        def getl(nums, n):\n",
    "            idmax = 0\n",
    "            idmin = len(nums)\n",
    "            l = list(enumerate(nums))\n",
    "            for i,x in l:\n",
    "                if x == n:\n",
    "                    if i > idmax:\n",
    "                        idmax = i\n",
    "                    if i < idmin:\n",
    "                        idmin = i\n",
    "            return idmax-idmin+1\n",
    "        m, n = getm(nums)\n",
    "        # print(m,n)\n",
    "        l = len(nums)\n",
    "        for i in range(len(n)):\n",
    "            if getl(nums,n[i]) < l:\n",
    "                l = getl(nums,n[i])\n",
    "        return l\n",
    "        \n",
    "\n",
    "        \n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        hlp = [[-1, 0] for _ in range(max(nums) + 1)]  # [第一次出现的下标, 出现次数]\n",
    "        degree, length = 1, 1\n",
    "        for i, num in enumerate(nums):\n",
    "            if hlp[num][0] > -1:\n",
    "                hlp[num][1] += 1\n",
    "                if hlp[num][1] > degree:\n",
    "                    degree = hlp[num][1]\n",
    "                    length = i - hlp[num][0] + 1\n",
    "                elif hlp[num][1] == degree:\n",
    "                    length = min(length, i - hlp[num][0] + 1)\n",
    "            else:\n",
    "                hlp[num] = [i, 1]\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        from collections import Counter, deque\n",
    "        def getm(nums):\n",
    "            l = Counter(nums)\n",
    "            # print(l)\n",
    "            n = []\n",
    "            m = l.most_common()[0][1]\n",
    "            for x,c in l.most_common():\n",
    "                if c < m:\n",
    "                    break\n",
    "                n.append(x)\n",
    "            return m, n\n",
    "        def getl(nums, n):\n",
    "            idmax = 0\n",
    "            idmin = len(nums)\n",
    "            l = list(enumerate(nums))\n",
    "            for i,x in l:\n",
    "                if x == n:\n",
    "                    if i > idmax:\n",
    "                        idmax = i\n",
    "                    if i < idmin:\n",
    "                        idmin = i\n",
    "            return idmax-idmin+1\n",
    "        m, n = getm(nums)\n",
    "        # print(m,n)\n",
    "        l = len(nums)\n",
    "        for i in range(len(n)):\n",
    "            if getl(nums,n[i]) < l:\n",
    "                l = getl(nums,n[i])\n",
    "        return l\n",
    "        \n",
    "\n",
    "        # i = len(nums)\n",
    "        # while i >= m:\n",
    "        #     n = nums.copy()\n",
    "        #     while len(n) >= i:\n",
    "        #         m1 = getm(n[:i])\n",
    "        #         if m1 == m:\n",
    "        #             # print(i,m,len(n),n[:i])\n",
    "        #             break\n",
    "        #         n.pop(0)\n",
    "        #     if len(n) < i:\n",
    "        #         return i+1\n",
    "        #     i -= 1\n",
    "        # if len(n) >= m:\n",
    "        #     return i+1\n",
    "        \n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        nums_count = collections.Counter(nums)\n",
    "        max_degree = max(nums_count.values())\n",
    "        li = [j for j, i in nums_count.items() if i == max_degree]\n",
    "        min_length = 50000\n",
    "        nums_dict = dict(enumerate(nums))\n",
    "        for i in li:\n",
    "            index_list = []\n",
    "            for j in nums_dict:\n",
    "                if nums_dict[j] == i:\n",
    "                    index_list.append(j)\n",
    "            start = min(index_list)\n",
    "            stop = max(index_list)\n",
    "            min_length = min(min_length, stop - start + 1)\n",
    "        return min_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        # 出现最多次数的元素，最左和最右的距离\n",
    "        ht = [0 for i in range(max(nums)+1)]\n",
    "        htd = [[-1, -1] for i in range(max(nums)+1)]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            ht[num] += 1\n",
    "            if htd[num][0] == -1:\n",
    "                htd[num][0] = i\n",
    "                htd[num][1] = i\n",
    "            else:\n",
    "                htd[num][1] = i\n",
    "        \n",
    "        maxDegree = max(ht)\n",
    "        ans = 600000\n",
    "        for i, d in enumerate(ht):\n",
    "            if d == maxDegree:\n",
    "                ans = min(ans, htd[i][1] - htd[i][0] + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        res = {}\n",
    "        key_set = []\n",
    "        max = 1\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num not in res:\n",
    "                res[num] = {'time':1, 'start':idx, 'end':idx}\n",
    "            else:\n",
    "                res[num]['time'] += 1\n",
    "                res[num]['end'] = idx\n",
    "                if res[num]['time'] > max:\n",
    "                    max = res[num]['time']\n",
    "\n",
    "        min_length = len(nums)\n",
    "        for key in set(nums):\n",
    "            if res[key]['time'] == max:\n",
    "                if res[key]['end'] - res[key]['start'] + 1 < min_length:\n",
    "                    min_length = res[key]['end'] - res[key]['start'] + 1\n",
    "        print(max)\n",
    "        return min_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        dic={}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in dic.keys():\n",
    "                dic[nums[i]]=[i]\n",
    "            else:\n",
    "                dic[nums[i]].append(i)\n",
    "        tmp=sorted(dic.values(),key=lambda x:len(x),reverse=True)\n",
    "        print(tmp)\n",
    "        if len(tmp[0])==1:\n",
    "            return 1\n",
    "        res=tmp[0][-1]-tmp[0][0]+1\n",
    "        if len(tmp)>1:\n",
    "            for i in range(1,len(tmp)):\n",
    "                if len(tmp[i])<len(tmp[0]):\n",
    "                    break\n",
    "                res=min(res,tmp[i][-1]-tmp[i][0]+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        index_dict = defaultdict(list)\n",
    "\n",
    "        mindist = 50000\n",
    "        maxdegree = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            index_dict[num].append(idx)\n",
    "            if len(index_dict[num]) > maxdegree:\n",
    "                # print('maxd', maxdegree, '->', count_dict[num], \":\", idx, num)\n",
    "                maxdegree = len(index_dict[num])\n",
    "                mindist = index_dict[num][-1] - index_dict[num][0] + 1\n",
    "            elif len(index_dict[num]) == maxdegree:\n",
    "                mindist = min(index_dict[num][-1] - index_dict[num][0] + 1, mindist)\n",
    "        print(maxdegree)\n",
    "        \n",
    "        return mindist\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        res = {}\n",
    "        key_set = []\n",
    "        max = 1\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num not in res:\n",
    "                res[num] = {'time':1, 'start':idx, 'end':idx}\n",
    "            else:\n",
    "                res[num]['time'] += 1\n",
    "                res[num]['end'] = idx\n",
    "                if res[num]['time'] > max:\n",
    "                    max = res[num]['time']\n",
    "\n",
    "        min_length = len(nums)\n",
    "        for key in set(nums):\n",
    "            if res[key]['time'] == max:\n",
    "                if res[key]['end'] - res[key]['start'] + 1 < min_length:\n",
    "                    min_length = res[key]['end'] - res[key]['start'] + 1\n",
    "        return min_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        count_dict = defaultdict(int)\n",
    "        index_dict = defaultdict(list)\n",
    "\n",
    "        mindist = 50000\n",
    "        maxdegree = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            count_dict[num] += 1\n",
    "            index_dict[num].append(idx)\n",
    "            if count_dict[num] > maxdegree:\n",
    "                # print('maxd', maxdegree, '->', count_dict[num], \":\", idx, num)\n",
    "                maxdegree = count_dict[num]\n",
    "                mindist = index_dict[num][-1] - index_dict[num][0] + 1\n",
    "            elif count_dict[num] == maxdegree:\n",
    "                mindist = min(index_dict[num][-1] - index_dict[num][0] + 1, mindist)\n",
    "        print(maxdegree)\n",
    "        \n",
    "        return mindist\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\r\n",
    "        length = 0\r\n",
    "        res = float('inf')\r\n",
    "        dic = {}\r\n",
    "        for i, v in enumerate(nums):\r\n",
    "            if v in dic:\r\n",
    "                dic[v].append(i)\r\n",
    "            else:\r\n",
    "                dic[v] = [i]\r\n",
    "            length = max(length, len(dic[v]))\r\n",
    "\r\n",
    "        for key in dic:\r\n",
    "            if len(dic[key]) == length:\r\n",
    "                res = min(res, dic[key][-1] - dic[key][0] + 1)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            mp[x].append(i)\n",
    "\n",
    "        size = max(len(v) for v in mp.values())\n",
    "\n",
    "        res = inf\n",
    "\n",
    "        for v in mp.values():\n",
    "            if len(v) == size:\n",
    "                res = min(res, v[-1] - v[0] + 1)\n",
    "        assert res != inf\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        maxx = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            d[nums[i]].append(i)\n",
    "            t = len(d[nums[i]])\n",
    "            if t > maxx:\n",
    "                maxx = t\n",
    "        \n",
    "        res = inf\n",
    "\n",
    "        for k, v in d.items():\n",
    "            if len(v) == maxx:\n",
    "                t = v[-1] - v[0] + 1\n",
    "                if t < res:\n",
    "                    res = t\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i, v in enumerate(nums):\n",
    "            d[v].append(i)\n",
    "        max_degree = len(max(d.values(), key=len))\n",
    "        # res = 0\n",
    "        res = float('inf')\n",
    "        for k, v in d.items():\n",
    "            if len(v) == max_degree:\n",
    "                res = min(res, v[-1] - v[0] + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in dic:\n",
    "                dic[nums[i]] = [i]\n",
    "            else:\n",
    "                dic[nums[i]].append(i)\n",
    "        # print(dic)\n",
    "        s = 0\n",
    "        for v in dic.values():\n",
    "            if len(v) > s:\n",
    "                s = len(v)\n",
    "        ans = len(nums)\n",
    "        for k in dic:\n",
    "            if len(dic[k]) == s:\n",
    "                ans = min(ans, dic[k][-1] - dic[k][0] + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        ndict = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            ndict[num].append(i)\n",
    "        # print(ndict)\n",
    "        # min\n",
    "        mx, count = 0, 0\n",
    "        for num in ndict.keys():\n",
    "            loc = ndict[num]\n",
    "            if mx < len(loc):\n",
    "                mx = len(loc)\n",
    "                count = loc[-1] - loc[0]\n",
    "            elif mx == len(loc):\n",
    "                count = min(count, loc[-1] - loc[0])\n",
    "        return count + 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "#         left, right = dict(), dict()\n",
    "#         counter = collections.Counter()\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num not in left:\n",
    "#                 left[num] = i\n",
    "#             right[num] = i\n",
    "#             counter[num] += 1\n",
    "#         degree = max(counter.values())\n",
    "#         res = len(nums)\n",
    "#         for k, v in counter.items():\n",
    "#             if v == degree:\n",
    "#                 res = min(res, right[k] - left[k] + 1)\n",
    "#         return res\n",
    "class Solution:\n",
    "    def findShortestSubArray(self, nums: List[int]) -> int:\n",
    "        #列表为value的字典\n",
    "        m = defaultdict(list)\n",
    "        #统计每个数字出现的次数\n",
    "        m_count = collections.Counter(nums)\n",
    "        #出现次数最多的次数\n",
    "        max_fre = max(m_count.values())\n",
    "        #对每个值出现的索引位置入该值为key的列表\n",
    "        for i in range(len(nums)):\n",
    "            m[nums[i]].append(i)\n",
    "        result = float(\"inf\")\n",
    "        for key, value in m.items():\n",
    "            #如果该值的出现次数等于出现次数最多的次数，那么对这个值的对应的value进行处理\n",
    "            if len(value) == max_fre:\n",
    "                #最大值和最小值之差就是其长度 - 1，目的是为了求最小间隔长度\n",
    "                if max(value) - min(value) < result:\n",
    "                    result = max(value) - min(value)\n",
    "        #返回其长度，这里为间隔+1\n",
    "        return result + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
